1. Field of Invention
The present invention relates generally to methods and apparatus for synchronization within a multi-threaded, object-based system. More particularly, the present invention relates to methods and apparatus for preventing monitors from being reclaimed during a garbage collection process when it is desired for the monitors to remain associated with their respective objects.
2. Description of the Related Art
An object that is suitable for use in an object-based environment generally includes a set of operations and a state that effectively remembers the effect of the operations. Since an object has at least some memory capability, an object differs from a function, which has substantially no memory capability. For example, a value returned by an operation associated with an object is dependent upon the state of the object as well as the arguments to the operation. As such, each invocation of an object may have a different result. In contrast, a value returned by a function is typically dependent only on the arguments to the function.
Within an object-based environment, threads are often used to satisfy requests for services. A thread may be thought of as a “sketch pad” of storage resources, and is essentially a single sequential flow of control within a computer program. In general, a thread, or a “thread of control,” is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is “pushed” on the execution stack of the thread. When the method returns, or is deactivated, the activation is “popped” from the execution stack. Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
In some object-based environments, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. Synchronization constructs such as locks, mutexes, semaphores, and monitors are often used to control access to shared resources, e.g., objects, such that only a single thread may invoke operations on a shared object at any given time.
In some virtual machines, when a thread wants to execute statements which require access to an object, the thread acquires a monitor associated with the object. A monitor, as will be understood by those skilled in the art, a mechanism which is arranged to enable one thread at a time to execute a specific region of code. Hence, a monitor may be considered to be a type of lock.
FIG. 1 is a diagrammatic representation of a multi-threaded, object-based system which includes threads, objects, and monitors. Within an object-based system 102, threads 104 may attempt to acquire, or lock, an object 108. In many systems, objects 108 are shared objects in that objects 108 may be part of a pool 110 of objects 108, stored on an object heap, that different threads 104 may attempt to access. In general, system 102 includes a freelist 112 of monitors 116 which is arranged to be shared, e.g., shared system-wide. Monitors 116, however, may either be global or thread-based. Freelist 112 is such that an object 108 may access freelist 112 to obtain a monitor 116. That is, object 108 uses freelist 112 to locate a suitable monitor 116 to associate with itself.
In a system which uses a set of monitors for a set of objects which is larger than the set of monitors, an object is typically associated with a monitor only when the object is alive or active. In other words, if an object is not being used by a thread, then the object does not need an associated monitor. If no objects reference a given monitor, then that monitor may effectively be reused, e.g., by another object. Since monitors are shared resources, disassociating effectively unused monitors from objects enables the resources associated with a computing system to be used more efficiently. The efficient use of resources, further, may lead to improved performance of the computing system.
Referring next to FIG. 2a, the associations between a thread, an object, and an associated monitor will be described. An object 204 has an associated monitor 206, which typically becomes associated with object 204 when a thread 208 acquires access to object 204. Thread 208 includes a reference 212, e.g., a pointer, to object 204 which, in turn, includes a link 214 or a reference to monitor 206. Monitor 206 includes its own link 216 or pointer to object 204. While the configuration of reference 212 and links 214, 216 may vary, reference 212 and links 214, 216 are often contents within a particular field of thread 208, object 204, and monitor 206, respectively. It should be appreciated that a field within monitor 206 which contains link 216 may be considered to be an object reference field.
Thread 208 includes a reference count (RC) which tracks the number of times thread 208 locks object 204 and, hence, “enters” monitor 206. Similarly, monitor 206 includes a lock count (LC) which is effectively the same as the reference count of thread 208. Thread 208 may generally execute a lock action, an unlock action, and a wait action. When thread 208 executes a lock action, thread 208 effectively acquire a claim on a lock (not shown) that is associated with object 204, and the reference count of thread 208 is incremented. An unlock action causes thread 208 to release a claim on the lock that is associated with object 204, and the reference count of thread 208 is decremented. During a wait action, the reference count of thread 208 is effectively temporarily set to zero, and the lock associated with object 204 effectively has no owner. A wait action such as an object wait operation in a Java™ programming environment developed by Sun Microsystems, Inc., of Palo Alto, Calif., generally causes an object to be unlocked, and may be executed to enable thread 208 to acquire access to another object and monitor (not shown). Once the wait action terminates, then the reference count of thread 208 is typically restored to a value it had prior to the wait state.
When object 204 is considered as having no owner, then monitor 206 may be reclaimed. That is, when monitor 206 has a lock count of zero and is considered as not being in use, monitor 206 may be reclaimed such that monitor 206 may become associated with another object. In the event that monitor 206 is reclaimed during a wait action, object 204 would no longer include a reference to monitor 206, as shown in FIG. 2b. If monitor 206, as shown in FIG. 2a, is reclaimed by a garbage collection during a wait action, then thread 208 will still require access to object 204 and, hence, a monitor after the wait action concludes. Newly associating a monitor with object 204 and, hence, thread 208 after a wait action is often expensive, as allocating synchronization constructs such as monitors may be time-consuming.
A monitor is generally subject to a garbage collection process because a monitor may contain a pointer to an object, e.g., link 216 of FIG. 2a. Since objects are routinely moved within memory space during a garbage collection, a garbage collector studies monitors because the pointers from monitors to objects may need to be updated to account for a move object. It should be appreciated that “reclaiming a monitor” generally includes removing pointers or links between the monitor and its associated object.
The reclamation of a monitor when a thread is in the midst of “using” an object and the monitor, e.g., during a wait action, is inefficient since the thread and the object would need an associated monitor as soon as the wait action concludes. The reassociation of a monitor with the thread and the object may be avoided if the original monitor is somehow kept associated with the object and the thread during the wait operation, even if a garbage collection process occurs during the wait operation. In other words, preventing a garbage collection process from reclaiming a monitor which has a lock count of zero due to an associated wait operation would effectively eliminate issues associated with having to reassociate a monitor with an object and a thread.
In addition, a system may require that a monitor not be reclaimed in order for the system to operate correctly. By way of example, when a thread waits on a monitor, the thread needs to be woken up when another thread performs a notify on that monitor. The wait operation may have changed the state of the monitor or the thread so that they are associated with each other. In such a case, it is important that the monitor not be used for another purpose until the wait operation has been completed, as the monitor is effectively still being used while the associated lock count is zero.
In order to prevent a monitor from being reclaimed during a wait operation or a similar operation, a counter is often set within the monitor that is only incremented when a claim to its associated object is made, and decremented when the claim is released. Such a counter would not be reset to zero during a wait action. While such a counter may effectively prevent a monitor from being reclaimed if a garbage collection occurs during a wait action, counters are often expensive to implement. For example, in a multi-threaded environment, reference counts may be expensive to implement without hardware support, like an atomic increment instruction.
A general system pointer may also be set to identify the monitor as being in use even if its lock count is zero. In other words, a monitor has a reference so that a garbage collector can find it. Such a reference may be a general system pointer, or an index into a table. In general, each reference to a monitor has only one thread that can modify it such that no additional locking or atomic operations are needed to lock the modify the monitor. The general system pointer may be studied by a garbage collector to identify the monitor as being in use, thereby preventing the monitor from being reclaimed. It should be appreciated, however, that while using a system pointer may be effective to prevent a monitor from being reclaimed, such a system pointer is expensive to implement, as it requires significant overhead.
Therefore, what is needed is an efficient method and apparatus for preventing monitors from being reclaimed during a wait operation. That is, what is desired is an inexpensive method for enabling a monitor to remain associated with an object during a garbage collection which occurs during a wait action or other similar action associated with the monitor.